package com.xcc.dataStructures.demo14_algapplication;

import java.util.Arrays;

/**
 * 克鲁斯卡尔算法
 * 求整个图中，能将所有的边全部连接，并且距离最小
 * 思路:1，将所有的能连接的边封装成一个边对象Edge(start,end,weight)
 * 2，将所有的边对象，按照weight属性按照升序进行排序
 * 3，遍历所有的边对象，只要满足其新增的边 不与  已知边构成回路
 * 判断回路(将没新增一条边，记录其end为当前start的终点)，终点重复则满足不构成回路
 */
public class Demo07_Kruskal {

    private static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        //顶点
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵
        int[][] matrix = {
                /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                /*A*/ {0, 12, INF, INF, INF, 16, 14},
                /*B*/ {12, 0, 10, INF, INF, 7, INF},
                /*C*/ {INF, 10, 0, 3, 5, 6, INF},
                /*D*/ {INF, INF, 3, 0, 4, INF, INF},
                /*E*/ {INF, INF, 5, 4, 0, 2, 8},
                /*F*/ {16, 7, 6, INF, 2, 0, 9},
                /*G*/ {14, INF, INF, INF, 8, 9, 0}};

        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        kruskalCase.kruskal();
    }

}

class KruskalCase {

    private static final int INF = Integer.MAX_VALUE;

    //顶点
    char[] vertexs;
    //邻接矩阵
    int[][] matrix;
    //各条边的记录
    Edge[] edges;
    //边的条数
    int edgeNum;
    //各顶点的终点，如果对应的值为0则表示终点为当前自身,如果就是指向终点所在的索引
    //如果两个顶点的终点对应的索引值相同则 连接构成回路
    int[] ends;

    /**
     * 构造函数
     */
    public KruskalCase(char[] vertexs, int[][] matrix) {
        this.vertexs = vertexs;
        this.matrix = matrix;
        this.ends = new int[vertexs.length];

        //求先存在的有效边的数量
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    edgeNum++;
                }
            }
        }

        //构建各条边的记录
        edges = new Edge[edgeNum];
        int index = 0;
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i + 1; j < vertexs.length; j++) {
                if (matrix[i][j] != INF) {
                    edges[index++] = new Edge(vertexs[i], vertexs[j], matrix[i][j]);
                }
            }
        }

    }

    /**
     * 克鲁斯卡尔算法
     */
    public void kruskal() {
        System.out.println("排序前:" + Arrays.toString(edges));
        sort(edges);
        System.out.println("排序后:" + Arrays.toString(edges));
        //最终的结果肯定是length-1条
        Edge[] res = new Edge[vertexs.length - 1];
        int index = 0;

        for (int i = 0; i < edges.length; i++) {
            int start = getIndexByChar(edges[i].start);
            int end = getIndexByChar(edges[i].end);
            //获取start结点的终点
            int startParent = getEnd(ends, start);
            //获取end结点的终点
            int endParent = getEnd(ends, end);
            //如果两个结点的 终点不是同一下标 则记录
            if (startParent != endParent) {
                //将当前边加入到结果集中
                res[index++] = edges[i];
                //同时更新start结点的终点为end结点的终点
                ends[startParent] = endParent;
            }
        }

        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i]);
        }

    }

    /**
     * 查询当前索引对应的终点的索引
     * 如果当前索引对应的终点为0，则直接返回自己，
     * 如果不为0记录向后找当前的终点  循环得到其终点
     * 例如: E的终点为F D的终点为E(此时会通过E找到F) 那么就是D和E的终点均为F
     *
     * @param end 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
     * @param i   表示传入的顶点对应的下标
     * @return 返回的就是 下标为i的这个顶点对应的终点的下标
     */
    public int getEnd(int[] end, int i) {
        while (end[i] != 0) {
            i = end[i];
        }
        return i;
    }

    /**
     * 获取字符顶点对应的索引
     *
     * @param c 当前字符
     */
    public int getIndexByChar(char c) {
        for (int i = 0; i < vertexs.length; i++) {
            if (c == vertexs[i]) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 排序
     */
    public void sort(Edge[] edges) {
        int min;
        for (int i = 0; i < edges.length; i++) {
            min = i;
            for (int j = i + 1; j < edges.length; j++) {
                if (edges[min].w > edges[j].w) {
                    min = j;
                }
            }
            //交换
            if (min != i) {
                Edge temp = edges[i];
                edges[i] = edges[min];
                edges[min] = temp;
            }
        }
    }

    /**
     * 遍历邻接矩阵
     */
    public void showMatrix() {
        for (int[] ints : matrix) {
            for (int anInt : ints) {
                System.out.printf("%10d\t", anInt);
            }
            System.out.println();
        }
    }
}

class Edge {
    //开始顶点
    char start;
    //结束顶点
    char end;
    //权重
    int w;

    public Edge(char start, char end, int w) {
        this.start = start;
        this.end = end;
        this.w = w;
    }

    @Override
    public String toString() {
        return "Edge[" + start +
                "->" + end +
                "=" + w + "]";
    }
}